package nfa;

import interfaces.Node;
import interfaces.Transition;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
import utilities.DotLanguageHelper;
import utilities.OperatorManager;

/**
 * @author Ricardo Sansores Aguilar
 */
public class NondeterministicFiniteAutomata {

    private String postfixRegularExpression;
    private AutomataNode firstNode;
    private AutomataNode lastNode;
    private List<AutomataNode> acceptanceNodes;
    private List<AutomataNode> nodeList;
    private boolean generalized;

    /**
     * Construye el autómata no determinista usando una expresión regular.
     * @param postfixRegularExpression 
     */
    public NondeterministicFiniteAutomata(String postfixRegularExpression) {
        generalized = false;
        this.postfixRegularExpression = postfixRegularExpression;
        //Lo primero es crear el estado inicial y anadirlo a la lista de nodos
        acceptanceNodes = new ArrayList<AutomataNode>();
        nodeList = new ArrayList<AutomataNode>();
        constructNFA();
    }

    /**
     * Construye el autómata no determinista usando una representación de arreglos de Strings que representan
     * la estructura del autómata.
     * @param states Los estados del autómata
     * @param firstState El estado inicial del autómata
     * @param aceptanceStates Los estados de aceptación del autómata
     * @param transitions Las transiciones del autómata
     */
    public NondeterministicFiniteAutomata(String[] states, String firstState, String[] aceptanceStates, String[] transitions) {        
        generalized = false;
        //Lo primero es crear todos los estados
        nodeList = new ArrayList<AutomataNode>();
        acceptanceNodes = new ArrayList<AutomataNode>();
        for (String state : states) {
            AutomataNode automataNode = new AutomataNode(state);
            if (Arrays.asList(aceptanceStates).contains(state)) {
                automataNode.setAceptanceNode(true);
                acceptanceNodes.add(automataNode);
            }
            nodeList.add(automataNode);
        }
        //Ahora asignamos el estado incial        
        firstNode = getNodeFromNodeList(firstState);
        //Finalmente recorremos todas las transiciones y las cableamos con sus respectivos nodos
        for (String transition : transitions) {
            //En la transición el primer caracter es el estado del que nace la transición
            Node inputNode = getNodeFromNodeList(transition.substring(0,transition.indexOf("_")));
            //La posición dos es el caracter de transición
            Character transitionCharacter = transition.charAt(transition.indexOf("_")+1);
            //Y a partir de la posición cinco están los nodos a los que lleva la transición
            String[] outputNodesNames = transition.substring(transition.indexOf("->")+2).split(",");
            for (String outputNodeName : outputNodesNames) {
                AutomataNode outputNode = getNodeFromNodeList(outputNodeName);
                //Añadimos la transición
                inputNode.addTransition(new AutomataTransition(outputNode, transitionCharacter));
            }
        }

    }

    //Este constructor sólo se usa internamente para crear autómatas deterministicos parciales.
    private NondeterministicFiniteAutomata(AutomataNode firstNode, AutomataNode lastNode) {
        this.firstNode = firstNode;
        this.lastNode = lastNode;
    }

    /**
     * Crea una representación DOT del autómata. La representación DOT es una representación
     * de una gráfica en un formato estándar que es comprendido por Graphviz.
     * @return Regresa un String que contiene la representación DOT del autómata
     */
    public String getDotRepresentation() {
        //El DotHelper no usa Nodos ni Transiciones de las
        return new DotLanguageHelper(firstNode, acceptanceNodes, nodeList).createDotString();
    }

    private void constructNFA() {
        //La estrategia para convertir una expresión regular en postfix a un autómata es tener un stack en el cual
        //vamos almacenando autómatas parciales que se van uniendo o concatenando hasta llegar al AutomataFinal
        //El stack puede contener o Caracteres o Autómatas finitos parciales
        Stack partialNFAStack = new Stack();
        for (int i = 0; i < postfixRegularExpression.length(); i++) {
            char actualChar = postfixRegularExpression.charAt(i);
            if (!OperatorManager.isOperator(actualChar)) {
                partialNFAStack.push(new Character(actualChar));                
                //Manejamos el caso especial en que la expresión regular es uno y sólo un caracter
                if(postfixRegularExpression.length() == 1){
                    firstNode = createNewFirstNode();
                    lastNode = createNewLastNode();
                    firstNode.addTransition(new AutomataTransition(lastNode, actualChar));
                }
                continue;
            }
            Object lastStackElement = partialNFAStack.pop();
            AutomataNode inputNode = null;
            AutomataNode outputNode = null;
            switch (actualChar) {
                case OperatorManager.OR_CHAR:
                    inputNode = createNewFirstNode();
                    outputNode = createNewLastNode();
                    if (lastStackElement instanceof Character && partialNFAStack.peek() instanceof Character) {
                        AutomataNode firstUnionNode = createNewNode();
                        AutomataNode secondUnionNode = createNewNode();
                        inputNode.addTransition(new AutomataTransition(firstUnionNode, (Character) lastStackElement));
                        inputNode.addTransition(new AutomataTransition(secondUnionNode, (Character) partialNFAStack.peek()));
                        firstUnionNode.addTransition(new AutomataTransition(outputNode, OperatorManager.EPSILON_CHAR));
                        secondUnionNode.addTransition(new AutomataTransition(outputNode, OperatorManager.EPSILON_CHAR));
                    } else if (lastStackElement instanceof NondeterministicFiniteAutomata && partialNFAStack.peek() instanceof NondeterministicFiniteAutomata) {
                        inputNode.addTransition(new AutomataTransition(((NondeterministicFiniteAutomata) lastStackElement).firstNode, OperatorManager.EPSILON_CHAR));
                        inputNode.addTransition(new AutomataTransition(((NondeterministicFiniteAutomata) partialNFAStack.peek()).firstNode, OperatorManager.EPSILON_CHAR));
                        ((NondeterministicFiniteAutomata) lastStackElement).lastNode.addTransition(new AutomataTransition(outputNode, OperatorManager.EPSILON_CHAR));
                        ((NondeterministicFiniteAutomata) partialNFAStack.peek()).lastNode.addTransition(new AutomataTransition(outputNode, OperatorManager.EPSILON_CHAR));
                    } else if (lastStackElement instanceof Character && partialNFAStack.peek() instanceof NondeterministicFiniteAutomata) {
                        NondeterministicFiniteAutomata partialNFA = (NondeterministicFiniteAutomata) partialNFAStack.peek();
                        inputNode.addTransition(new AutomataTransition(partialNFA.firstNode, OperatorManager.EPSILON_CHAR));
                        inputNode.addTransition(new AutomataTransition(outputNode, (Character) lastStackElement));
                        partialNFA.lastNode.addTransition(new AutomataTransition(outputNode, OperatorManager.EPSILON_CHAR));
                    } else {
                        NondeterministicFiniteAutomata partialNFA = (NondeterministicFiniteAutomata) lastStackElement;
                        inputNode.addTransition(new AutomataTransition(partialNFA.firstNode, OperatorManager.EPSILON_CHAR));
                        inputNode.addTransition(new AutomataTransition(outputNode, (Character) partialNFAStack.peek()));
                        partialNFA.lastNode.addTransition(new AutomataTransition(outputNode, OperatorManager.EPSILON_CHAR));
                    }
                    partialNFAStack.pop();
                    break;
                case OperatorManager.CONCATENATION_CHAR:
                    if (lastStackElement instanceof Character && partialNFAStack.peek() instanceof Character) {
                        inputNode = createNewFirstNode();
                        AutomataNode middleNode = createNewNode();
                        outputNode = createNewLastNode();
                        inputNode.addTransition(new AutomataTransition(middleNode, (Character) partialNFAStack.peek()));
                        middleNode.addTransition(new AutomataTransition(outputNode, (Character) lastStackElement));                       
                    } else if (lastStackElement instanceof NondeterministicFiniteAutomata && partialNFAStack.peek() instanceof NondeterministicFiniteAutomata) {
                        NondeterministicFiniteAutomata partialNFAinput = (NondeterministicFiniteAutomata) partialNFAStack.peek();
                        NondeterministicFiniteAutomata partialNFAoutput = (NondeterministicFiniteAutomata) lastStackElement;
                        inputNode = firstNode = partialNFAinput.firstNode;
                        outputNode = partialNFAoutput.lastNode;
                        acceptanceNodes.clear();
                        acceptanceNodes.add(partialNFAoutput.lastNode);
                        partialNFAinput.lastNode.addTransition(new AutomataTransition(partialNFAoutput.firstNode, OperatorManager.EPSILON_CHAR));                        
                    } else if (lastStackElement instanceof Character && partialNFAStack.peek() instanceof NondeterministicFiniteAutomata) {
                        NondeterministicFiniteAutomata partialNFA = (NondeterministicFiniteAutomata) partialNFAStack.peek();
                        outputNode = createNewLastNode();
                        inputNode = firstNode = partialNFA.firstNode;
                        //FIXME en lugar de crear un nuevo nodo debería unir nodo final y nodo inicial pero para rápido por ahora
                        partialNFA.lastNode.addTransition(new AutomataTransition(outputNode, (Character) lastStackElement));
                    } else {
                        NondeterministicFiniteAutomata partialNFA = (NondeterministicFiniteAutomata) lastStackElement;
                        inputNode = createNewFirstNode();
                        inputNode.addTransition(new AutomataTransition(partialNFA.firstNode, (Character) partialNFAStack.peek()));
                        outputNode = partialNFA.lastNode;
                        acceptanceNodes.clear();
                        acceptanceNodes.add(outputNode);
                    }
                    partialNFAStack.pop();
                    break;
                case OperatorManager.KLEEN_CHAR:
                    if (lastStackElement instanceof Character) {
                        inputNode = outputNode = createNewFirstNode();
                        acceptanceNodes.clear();
                        acceptanceNodes.add(firstNode);
                        inputNode.addTransition(new AutomataTransition(inputNode, (Character) lastStackElement));                                                
                    } else {
                        NondeterministicFiniteAutomata partialNFA = (NondeterministicFiniteAutomata) lastStackElement;
                        inputNode = partialNFA.firstNode;
                        outputNode = partialNFA.lastNode;
                        inputNode.addTransition(new AutomataTransition(outputNode, OperatorManager.EPSILON_CHAR));   
                        outputNode.addTransition(new AutomataTransition(inputNode, OperatorManager.EPSILON_CHAR)); 
                    }
                    break;
            }
            //Creamos el nuevo autómata y lo metemos en la pila
            partialNFAStack.push(new NondeterministicFiniteAutomata(inputNode, outputNode));
        }
    }

    private AutomataNode createNewFirstNode() {
        AutomataNode inputNode = createNewNode();
        firstNode = inputNode;
        return inputNode;
    }

    private AutomataNode createNewLastNode() {
        AutomataNode outputNode = createNewNode();
        acceptanceNodes.clear();
        acceptanceNodes.add(outputNode);
        return outputNode;
    }

    private AutomataNode createNewNode() {
        AutomataNode outputNode = new AutomataNode("Q" + nodeList.size());
        nodeList.add(outputNode);
        return outputNode;
    }

    private void generalizeFirstNode() {
        AutomataNode oldFirstNode = firstNode;
        firstNode = new AutomataNode("INIT");
        firstNode.addTransition(new GeneralizedAutomataTransition(oldFirstNode, OperatorManager.EPSILON_CHAR + ""));
        nodeList.add(firstNode);
    }

    private void generalizeTransitions() {
        //Aprovechamos para transformar todas las transiciones de tipo AutomataTransition a GeneralizedAutomataTransition
        //que en lugar de usar un caracter para hacer una transición usan una expresión regular
        for (AutomataNode node : nodeList) {
            //Hacemos un respaldo de las transiciones
            List<? extends Transition> transitions = node.getTransitions();
            //Y las desacoplamos del nodo
            node.clearTransitions();
            for (Transition transition : transitions) {
                //Buscamos si ya existe una transición cuyo output Node sea el mismo que de la transición actual
                Transition transitionByOutputNode = node.getTransitionByOutputNode(transition.getToNodeName());
                if (transitionByOutputNode == null) {
                    //Significa que no existe ninguna transición con ese nombre así que la creamos y la asignamos al nodo
                    node.addTransition(new GeneralizedAutomataTransition(getNodeFromNodeList(transition.getToNodeName()), transition.getTransitionLabel()));
                } else {
                    //Ya existe una transición, nada más unimos ambas transiciones usando el operador or tomando en cuenta los paréntesis necesarios
                    transitionByOutputNode.setTransitionLabel(transitionByOutputNode.getTransitionLabel().replace(OperatorManager.CLOSE_ROUND_BRACKET_CHAR + "", ""));
                    transitionByOutputNode.setTransitionLabel(transitionByOutputNode.getTransitionLabel().replace(OperatorManager.OPEN_ROUND_BRACKET_CHAR + "", ""));
                    String union = transitionByOutputNode.getTransitionLabel() + OperatorManager.OR_CHAR + transition.getTransitionLabel();
                    transitionByOutputNode.setTransitionLabel(OperatorManager.OPEN_ROUND_BRACKET_CHAR + union + OperatorManager.CLOSE_ROUND_BRACKET_CHAR);
                }
            }
        }
    }

    private AutomataNode getNodeFromNodeList(String nodeName) {
        for (AutomataNode node : nodeList) {
            if (node.getName().equals(nodeName)) {
                return node;
            }
        }
        return null;
    }

    /**
     * Generaliza el autómata incluyendo un nuevo estado de inicio y unificando todos los estados de aceptación.
     * También incluye un operador OR a todas las transiciones que coinciden en nodo de entrada y salida.
     */
    public void generalizeAutomata() {
        //Al crear un GNFA de un NFA necesitamos hacer una transición al estado inicial con epsilon
        generalizeFirstNode();
        //Ahora tenemos que quitar todos los estados de aceptación y unificarlos en uno sólo.
        unifyAceptanceNodes();
        //Finalmente todas las transiciones cuyo nodo inicial y final coincida deben de unirse
        generalizeTransitions();
        //Marcamos el automata como generalizado
        generalized = true;
    }

    private List<AutomataNode> getRelatedNodesOfNodeToRip(AutomataNode node) {
        List<AutomataNode> nodesRelatedToRipNode = new ArrayList<AutomataNode>();
        for (AutomataNode actualNode : nodeList) {
            for (Transition actualTransition : actualNode.getTransitions()) {
                //Si el nodo tiene una transición que va al nodo que queremos eliminar lo incluimos en la lista siempre y cuando
                //no sea una transición que vaya del nodo al mismo nodo, en otras palabras una cerradura de klenee
                if (actualTransition.getToNodeName().equals(node.getName()) && actualNode != node) {
                    nodesRelatedToRipNode.add(actualNode);
                }
            }
        }
        return nodesRelatedToRipNode;
    }

    private void unifyAceptanceNodes() {
        AutomataNode unifiedAceptanceNode = new AutomataNode("LAST");
        unifiedAceptanceNode.setAceptanceNode(true);
        nodeList.add(unifiedAceptanceNode);
        for (AutomataNode aceptanceNode : acceptanceNodes) {
            aceptanceNode.setAceptanceNode(false);
            aceptanceNode.addTransition(new GeneralizedAutomataTransition(unifiedAceptanceNode, OperatorManager.EPSILON_CHAR + ""));
        }
        acceptanceNodes.clear();
        acceptanceNodes.add(unifiedAceptanceNode);
    }

    /*
     * Crea una expresión regular a partir de autómata. Si el autómata no se encuentra generalizado
     * éste método intentará generalizarlo. Es importante notar que una vez ejecutado éste método se
     * pierde completamente la estructura del autómata.
     * FIXME: Deberíamos usar una copia del autómata para evitar perderlo. Por la complejidad de éste objeto
     * para hacer la copia necesitamos utilizar la técnica de serialización deserialización para generar un deepcopy.
     */
    public String generateRegularExpressionFromAutomata() {
        //Nos aseguramos que el autómata se encuentre generalizado y si no lo está lo generalizamos
        if (!generalized) {
            generalizeAutomata();
        }
        //Ahora vamos quitando uno a uno los nodos hasta quedarnos sólo con INIT y LAST    
        //El for itera sobre un arreglo para evitar problemas de concurrencia
        for (AutomataNode node : nodeList.toArray(new AutomataNode[]{})) {
            //No eliminaremos ni el nodo INIT ni LAST así que simplemente los ignoramos
            //Es importante notar que hacemos un get(0) ya que al estar generalizado el automata
            //unicamente tiene un estado de aceptación.
            if (node == firstNode || node == acceptanceNodes.get(0)) {
                continue;
            } else {
                //Eliminamos el nodo concatenando en las transiciones resultantes la expresión regular resultante
                ripNodeCreatingRegularExpression(node);
            }
        }
        //Al salir de éste método sólo debemos tener dos nodos con una sóla transición entre ellos
        return firstNode.getTransitions().get(0).getTransitionLabel();
    }

    private void ripNodeCreatingRegularExpression(AutomataNode node) {
        //Para poder eliminar el nodo necesito obtener una lista de todos los nodos que tengan
        //transiciones hacia el nodo que deseo eliminar
        List<AutomataNode> nodesRelatedToRipNode = getRelatedNodesOfNodeToRip(node);
        //Obtenemos las transiciones de klenee, aquellas que salen del nodo y llegan a sí mismo
        Transition kleneeTransition = (Transition) node.getTransitionByOutputNode(node.getName());
        String transition = "";
        //Ahora tomamos el nodo relacionado y lo desconectamos del nodo que deseamos eliminar
        //conectándolo a todos los nodos de salida y concatenando las expresiones regulares
        for (AutomataNode relatedNode : nodesRelatedToRipNode) {
            Transition transitionToNode = relatedNode.getTransitionByOutputNode(node.getName());
            transition = transitionToNode.getTransitionLabel();
            relatedNode.getTransitions().remove(transitionToNode);
            for (Transition transitionToRip : node.getTransitions()) {
                //Si la transición de salida es hacia el mismo nodo no la tomamos en cuenta ya que se considerará
                //en las otras otras transiciones concatenando una cerradura de klenee
                if (transitionToRip.getToNodeName().equals(node.getName())) {
                    continue;
                }
                if (kleneeTransition != null) {
                    relatedNode.addTransition(new GeneralizedAutomataTransition(((GeneralizedAutomataTransition) transitionToRip).getOutputNode(),
                            OperatorManager.OPEN_ROUND_BRACKET_CHAR
                            + transition
                            + kleneeTransition.getTransitionLabel()
                            + OperatorManager.KLEEN_CHAR
                            + transitionToRip.getTransitionLabel()
                            + OperatorManager.CLOSE_ROUND_BRACKET_CHAR));
                } else {
                    relatedNode.addTransition(new GeneralizedAutomataTransition(((GeneralizedAutomataTransition) transitionToRip).getOutputNode(),
                            OperatorManager.OPEN_ROUND_BRACKET_CHAR
                            + transition
                            + transitionToRip.getTransitionLabel()
                            + OperatorManager.CLOSE_ROUND_BRACKET_CHAR));
                }
            }
        }
        //Ya que el nodo no tiene una sóla transición lo podemos eliminar
        nodeList.remove(node);
        //Para acelerar la recolección de basura colocamos el nodo en null
        node = null;
        //Finalmente volvemos a generalizar las transiciones
        generalizeTransitions();
    }
}
